package com.yww.algorithm.recursion;

/**
 * @author yww
 * @description 递归插入排序
 * @since 2024/1/31 14:16
 */
public final class InsertionSort {
    public static void sort(int[] arr) {
        insertion(arr, 0, arr.length - 1);
    }

    private static void insertion(int[] arr, int low, int high) {
        if (low > high) {
            return;
        }
        // 待插入元素
        int temp = arr[low];
        // 最后一个有序元素索引
        int i = low - 1;

        while (i >= 0 && arr[i] > temp) {
            // 往后移
            arr[i + 1] = arr[i];
            i--;
        }

        // 找到待插入位置
        if (i + 1 != low) {
            arr[i + 1] = temp;
        }

        // 递归，扩大有序区间
        insertion(arr, low + 1, high);
    }
}
